package main.Q1501_1600;

public class Q1541_1550 {
    public static void main(String[] args) {
        System.out.println("Question1541：");
        System.out.println("Question1542：");
        System.out.println("Question1543：");
        System.out.println("Question1544：");
        System.out.println("Question1545：");
        System.out.println("Question1546：");
        System.out.println("Question1547：");
        System.out.println("Question1548：");
        System.out.println("Question1549：");
        System.out.println("Question1550：");
    }
}

class Question1545{
    public char findKthBit(int n, int k) {
        //既然给出了递推公式,尝试一下dp
        String[] dp = new String[n];
        dp[0] = "0";
        //dp[1] = "011";
        for(int i=1;i<n;i++){
            dp[i] = dp[i-1]+"1"+reverse(invert(dp[i-1]));
        }
        return dp[n-1].charAt(k-1);
    }
    public String invert(String str){
        char[] arr = str.toCharArray();
        for(int i=0;i<arr.length;i++){
            if(arr[i]=='1') arr[i] = '0';
            else arr[i] = '1';
        }
        return new String(arr);
    }
    public String reverse(String str){
        char[] arr = str.toCharArray();
        int left = 0;
        int right = arr.length-1;
        while(left<right){
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
        return new String(arr);
    }
}